Due to the increasing need for rapid matching capabilities, in networking hardware equipment for example, content addressable memories (CAMs) continue to proliferate. A CAM may perform matching functions by applying a search key or “comparand” to a table of stored data values. A CAM may then determine if any of the data values match a given search key.
CAM devices may take a variety of forms. As but a few of the possible examples, some CAM devices are based on particular types of CAM cells. Such cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic RAM (DRAM) type cells. Alternate approaches may include RAM arrays, or the like, with separate matching circuits and/or matching processes executed by a processor, or the like.
Conventional CAM devices may include both binary and ternary CAM devices. Binary CAM devices can provide a bit-by-bit comparison between a stored data value and a search key. Ternary CAM devices can provide maskable compare operations that can selectively exclude predetermined bits of a data value from a compare operation.
Typically, a conventional CAM device can generate match indications for each valid entry. That is, each entry can be compared with an applied search key value. If a search key value matches a stored data value, a match (or “hit”) indication may be generated for the entry. Conversely, if a key value does not match a stored data value, a mismatch (or “miss”) indication may be generated for the entry.
Match results in a CAM device may include single match results that can be generated when a single entry matches an applied key value, as well as multiple match results, that may be generated when more than one entry matches an applied key value.
Conventionally, when a CAM device generates multiple match results, a priority encoder, or the like, can prioritize from among such multiple matches and output an indication corresponding to a single match entry. Typically, priority from among multiple matching entries can be established according to entry address (e.g., lowest address corresponds to highest priority).
While a priority encoder, or the like, can select from among multiple matching entries, it can be desirable to identify other lower priority matching entries. A conventional approach to identifying lower priority addresses in a multiple match case will now be described.
Referring now to FIGS. 9A–9C, a conventional content addressable memory (CAM) device is set forth and designated by the general reference character 900. A conventional CAM device 900 may include a number of entries 902-0 to 902-n, each for storing data values for comparison with a search key value. A CAM device 900 may also include a match indicator bit 904-0 to 904-n corresponding to each entry (902-0 to 902-n). The function of match bits (904-0 to 904-n) will be described in more detail below.
Entries (902-0 to 902-n) may each generate a match indication M0 to Mn. Match indications (M0 to Mn) can indicate when data values in a corresponding entry (902-0 to 902-n) match an applied search key value. Match indications may be prioritized and encoded into an index value by a priority encoder 910.
A search key value KEY may be applied to entries (902-0 to 902-n) from a search key input 906. Along with a search key, a key match bit 908 may be applied to match bits (904-0 to 904-n) of entries (902-0 to 902-n). Conventionally, match bits (904-0 to 904-n) can function in the same way as a data value bit within an entry. If a key match bit 908 does not match a match bit (904-0 to 904-n) a match indication can be forced to a “miss” state. Thus, in the conventional arrangement of FIGS. 9A to 9C, a match indication can be in a “hit” state when both a data value and a corresponding match bit for the entry matches a search key value and key match bit, respectively.
In FIG. 9A it is assumed that an applied search key value KEY matches data values stored in entries 902-1, 902-3 and 902-4. In addition, prior to the application of a search key value KEY, match bits (904-0 to 904-n) can all be set to a same value as key match bit 908. Thus, such match bits (904-0 to 904-n) may not generate a mismatch indication. Consequently, a CAM device 900 may have a multiple match state, shown by match indications M1, M3 and M4 having a “HIT” status.
A priority encoder 910 may prioritize resulting multiple match indications. In FIGS. 9A to 9C it will be assumed that physical priority is established with entry 902-0 having a highest priority and entry 902-n having a lowest priority. Accordingly, active match indication M1 can be encoded into an index value INDEX1.
In the conventional approach shown in FIGS. 9A to 9C, following the generation of multiple “HIT” match indications, match bits for all but the highest priority matching entry and a key match bit 908 can be changed to differ from match bits of non-matching entries. This is illustrated in FIG. 9B by match bits for lower priority matching entries 904-3 and 904-4, and key match bit 908 being changed from a “1” to a “0”.
A subsequent search may then be performed with new match bit and key match bit values. This is shown in FIG. 9C.
In FIG. 9C, a same key value KEY as shown in FIG. 9A may be applied from a key input 906 to entries (902-0 to 902-n). In addition, a key match bit 908 may be applied to match bits (904-0 to 904-n). Due to a change in match bit values and a key match bit value as noted above, non-matching entries and a highest priority entry from the previous search as described are prevented from generating “HIT” match indications. Consequently, a second highest priority active match indication M3 may be prioritized and encoded by priority encoder 910 to generate an index value INDEX3. In this way, a next higher priority match result for a multiple match case may be extracted.
A conventional search operation may continue by changing match bit 904-3 from a “0” to a “1” and then searching once again with a same search key and key match bit value. Such a search may result in third highest priority match indication M4 being encoded into an in index value INDEX4 (not shown). Such an operation may continue in this fashion until all match results are extracted.
A drawback to the conventional approach noted above can be added time in executing the function and/or added complexity in circuits. In particular, multiple additional write operations may be necessary to set match bits in matching entries and to set a key match bit. In addition, a write operation may be necessary to set the match bit of each matching entry as lower priority matches are extracted.
Yet another drawback to such a conventional approach can be lack of flexibility in operation. In order to extract multiple match results, the state of the conventional CAM is essentially monopolized by the process. That is, while multiple match values are extracted, other search operations may not be performed as the setting of a key match bit can prevent a search of non-matching entries and/or higher priority entries that have been previously extracted.
In light of the above, it would be desirable to arrive at some way of extracting multiple match results that may be more flexible and/or faster than conventional approaches.
Additionally, it is always desirable to provide new search features in a CAM device for targeting searches to smaller search spaces (e.g., fewer numbers of entries). Such restricted search approaches may yield results faster than conventional approaches that do not restrict a search space. In addition or alternatively, restricting a search space may reduce power consumption by excluding some entries from search operations.
It is also desirable to arrive at ways of reducing overall device size, as such size reductions can translate to cost savings in an integrated circuit device.